package ca.etsmtl.log320;

import java.util.Vector;

public class Backtracking {

	int tabElem[] = new int[9];
	int compteTab = 9;
	
	public Backtracking( ) {
		//this.sudoku=sudoku;
		//this.nbrOfElementPlace=nbrOfElementPlace;
	}
	
	public boolean calculateAnswer(/*Integer[][] grille,*/ int[][] resultat) {
		for(int i=0; i<9 ; i++){
			tabElem[i]=9;
		}
		compteTab = 9;
        return calcul(resultat, 0, 0);
	}

	
	boolean calcul(int[][] g, int x, int y)
	{
		//System.out.println("calcul: " + x + " : " + y )
	    if (y > 8)
	        return true;
	 	 
	    if (g[x][y] != 0) {
	    	if(x > 7)
	    		return calcul(g, 0, y+1);//changement de colonne
	    	return calcul(g, x+1, y);//gauche � droite
	    }
	    
	    for(int n=1; n<=9; n++)
	    {
	    	if(compteTab!=0){
		    	if(tabElem[n-1]!=0){
				       if (estValide(g, x, y, n))
				       {
				            g[x][y] = n;
				            tabElem[n-1]-=1;
				            if(tabElem[n-1]==0){
				            	compteTab-=1;
				            }
					    	if(x > 7) {
					    		if(calcul(g, 0, y+1))//changement de colonne
					    			return true;
					    	} else if(calcul(g, x+1, y)) {//gauche � droite
					    		return true;
					    	}
					    	 g[x][y] = 0;
					         if(tabElem[n-1]==0){
					            compteTab+=1;
					         }
					            tabElem[n-1]+=1;
				        }
				    }
	    	}
	    	else{
	    		return true;
	    	}
	    }
	    	
	    
	 
	    return false;
	}
    public boolean estValide(int[][] grille, int x, int y, int k){
    	for(int i=0; i<9; i++){
    		//present sur ligne
    		if(grille[x][i] == k)
    			return false;
    		//pr�sent sur colonne
    		if(grille[i][y] == k)
    			return false;
    	}
    	//pr�sent dans bloc
        int xBloc = (x/3)*3;
        int yBloc = (y/3)*3;
        
        for (int i = xBloc; i < xBloc + 3; i++)
            for (int j = yBloc; j < yBloc + 3; j++)
                if (grille[i][j] == k)
                    return false;
    	return true;
    	
	}
}